A variety of specialized software tools have been developed to meet the challenges of designing and manufacturing more complex and higher performance electronic systems such as printed circuit boards and integrated circuits (ICs). Part of the design process is the simulation of such circuits in order to check the integrity of the circuit design and to predict circuit behavior. For example, it may be desired to simulate an integrated circuit in order to understand the inductive effects of the circuit design. Inductive effects are important in determining power supply integrity, performing timing and noise analysis (especially for global clock networks), and analyzing signal buses and supply grids for high-performance microprocessors. In addition, operation of the circuit at high frequencies introduces coupling effects between components, such as mutual inductance, that must be taken into account during simulation in order to ensure correct results. Moreover, inductive effects have become increasingly impactful as integrated circuit technologies shrink further and low-k dielectrics are used to diminish capacitive effects.
Methods for simulation of large integrated circuits generally focus on the solving linear systems that describe the circuits. These linear systems use matrices to model circuits having a number of nodes and branches. Matrices are used to model node conductances, node capacitances, excitations from independent current sources, self-inductances of each branch, and mutual inductances between branches. The main limiting factor in simulation of such circuits is the inductance matrix, which is a dense matrix—compared to the conductance and capacitance matrices—because mutual inductances between the individual branches is taken into account. As a consequence, the computational and memory requirements of the algorithm used to solve the linear systems are greatly increased.
Certain solutions have been proposed to solve the computation problems presented by the dense linear systems describing the integrated circuits. One approach is to use sparsification techniques to reduce the size of the inductance matrix. The density of a matrix (also known as the sparsity) is the fraction of non-zero elements compared to the total number of elements. Generally, sparse matrices will have a large number of off-diagonal elements equal to zero. As integrated circuits grow large and mutual inductances are taken into account, the inductance matrix grows dense. Sparsification techniques attempt to reduce the size of the inductance matrix to make solving the linear system more efficient. However, sparsification techniques are not based on mathematically established methodologies, and often result in a loss in accuracy. Moreover, sparsification can cause the modified linear system to become unstable. Further approaches attempt to use model-order reduction techniques to simplify the system, such as those demonstrated in Kaushik Gala et al., Inductance 101: Analysis and Design Issues, Proceedings of the 38th Annual Design and Automation Conference, ACM 2001. These approaches have also faced difficulties, as many model-order reduction techniques are not effective when applied to circuits with large number of ports, which thus limits their applicability to large-scale circuit simulations.
Finally, many of these approaches combine with a direct method of solving the linear systems. Direct methods are often based on matrix factorization. The computational and memory requirements of these direct methods increase quadratically with the dimensions of the matrices in the linear system. In addition, the factorization step must be performed at every frequency point in the AC analysis, which increases the complexity of the analysis.
There is therefore a need for a new approach for simulating high speed integrated circuits that does not suffer from the drawbacks of prior approaches.